#include <stdio.h>
#include <stdlib.h>
#include "queue.h"

// #define MaxSize 10

typedef struct TreeNode *BinTree;
typedef BinTree Position;

struct TreeNode{
    int Data;
    BinTree Left;
    BinTree Right;
};

/**
 * 先序遍历：
 *  ①访问根结点
 *  ②先序遍历其左子树
 *  ③先序遍历其右子树
 */
void PreOrderTraversal(BinTree BT);
/**
 * 中序遍历：
 *  ①中序遍历其左子树
 *  ②访问根结点
 *  ③中序遍历其右子树
 */
void InOrderTraversal(BinTree BT);
/**
 * 后序遍历：
 *  ①后序遍历其左子树
 *  ②后序遍历其右子树
 *  ③访问根结点
 */
void PostOrderTraversal(BinTree BT);
//层序遍历
void LevelOrderTraversal(BinTree BT);
//线索二叉树的插入(已实现)
BinTree Insert(int X, BinTree BST);
//线索二叉树的删除(还未实现)
BinTree Delete(int X, BinTree BST);

int main(){
    
    BinTree bt = Insert(2, NULL);
    Insert(1, bt);
    Insert(3, bt);
    printf("先序遍历:");
    PreOrderTraversal(bt);
    printf("\n");
    printf("中序遍历:");
    InOrderTraversal(bt);
    printf("\n");
    printf("后序遍历:");
    PostOrderTraversal(bt);
    printf("\n");
    //层序遍历暂未实现
    // printf("层序遍历:");
    // LevelOrderTraversal(bt);
    // printf("\n");
    return 0;

}

void PreOrderTraversal(BinTree BT){
    if(BT){
        printf("%d", BT->Data);
        PreOrderTraversal(BT->Left);
        PreOrderTraversal(BT->Right);
    }
}

void InOrderTraversal(BinTree BT){
    if(BT){
        InOrderTraversal(BT->Left);
        printf("%d", BT->Data);
        InOrderTraversal(BT->Right);
    }
}

void PostOrderTraversal(BinTree BT){
    if(BT){
        PostOrderTraversal(BT->Left);
        PostOrderTraversal(BT->Right);
        printf("%d", BT->Data);
    }
}

void LevelOrderTraversal(BinTree BT){
    Queue Q;
    // BinTree T = (BinTree)malloc(sizeof(struct TreeNode));
    BinTree T = BT;
    if(!BT) return;/* 若是空树则直接返回*/
    Q =  creatQueue(MaxSize);//创建并初始化队列
    addQ(Q, BT->Data);
    while( !isEmptyQ(Q)){
        //伪代码中deleteQ返回的是树的节点，不是单独的int Data,此处deleteQ要改写
        T->Data = deleteQ(Q);
        printf("%d\n", T->Data);//访问取出队列的结点
        if(T->Left) addQ( Q, T->Left->Data);
        if(T->Right) addQ( Q, T->Right->Data);
    }
}

BinTree Insert(int X, BinTree BST){
    if(!BST){
        //若原树为空，生成并返回一个结点的二叉搜索树
        BST = (BinTree)malloc(sizeof(struct TreeNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    }else{
        //开始找要插入元素的位置
        if(X<BST->Data){
            //递归插入左树
            BST->Left = Insert(X, BST->Left);
        }else if(X>BST->Data){
            //递归插入右树
            BST->Right = Insert(X, BST->Right);
        }
        //else X已经存在，什么都不做
    }
    return BST;
}

BinTree Delete(int X, BinTree BST){
    Position Tmp;
    if(!BST) printf("要删除的元素未找到");
    else if( X < BST->Data)
        BST->Left = Delete( X, BST->Left);
    else if( X > BST->Data)
        BST->Right = Delete( X, BST->Right);
    else{
        //找到要删除的结点
        if(BST->Left && BST->Right){
            //在右子树中找到最小的元素填充删除结点
            Tmp = FindMin(BST->Right);
            BST->Data = Tmp->Data;
            //在删除结点的右子树中删除最小元素
            BST->Right = Delete(BST->Data, BST->Right);
        }else{
            //被删除结点有一个或无子结点
            Tmp = BST;
            if( !BST->Left)
                //有右孩子或无子结点
                BST = BST->Right;
            else if(!BST->Right)
                //有左孩子或无子结点
                BST = BST->Left;
            free(Tmp);
        }
    }   
    return BST; 
}